package Lee_code;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author blh
 * @date 2024年06月24日 13:19
 */
public class Lee_216_624 {
    TreeNode lowestCommon;
    List<List<TreeNode>> resList = new ArrayList<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        List<TreeNode> list = new LinkedList<>();
        list.add(root);
        search(p, list, root);
        search(q, list, root);
        List<TreeNode> pList = resList.get(0);
        List<TreeNode> qList = resList.get(1);

        TreeNode sameNode = new TreeNode();
        for (TreeNode node : pList) {
            for (TreeNode treeNode : qList) {
                if (node.equals(treeNode)) {
                    sameNode = node;
                }
            }
        }
        return sameNode;
    }

    private void search(TreeNode target, List<TreeNode> list, TreeNode curNode) {
        if (curNode.equals(target)) {
            resList.add(new ArrayList<>(list));
        }
        // 不是目标

        // 左子树
        if (curNode.left != null) {
            list.add(curNode.left);
            search(target, list, curNode.left);
            list.remove(list.size() - 1);
        }
        // 右子树
        if (curNode.right != null) {
            list.add(curNode.right);
            search(target, list, curNode.right);
            list.remove(list.size() - 1);
        }
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q || root == null) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 如果left 和 right都不为空，说明此时root就是最近公共节点
        // 如果left为空，right不为空，就返回right，说明目标节点是通过right返回的，反之亦然。
        if (left != null && right != null) {
            return root;
        }
        if (left == null) {
            return right;
        }
        return left;
    }

}
